|
|
Řízená syntaktická analýza
Wolf, Dominik ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce se zabývá rozšířenými modely bezkontextových gramatik a zkoumá možnosti jejich úpravy a využití pro deterministickou syntaktickou analýzu pomocí metod hluboké syntaktické analýzy struktur, které nejsou bezkontextové. Zavádí upravený bezkontextový model LL programovaných gramatik a hlubokého zásobníkového automatu, umožňující deterministickou syntaktickou analýzu těchto struktur.
|
|
| |
|
|
Cestami řízené gramatiky
Adamec, Ondřej ; Soukup, Ondřej (oponent) ; Křivka, Zbyněk (vedoucí práce)
Tato diplomová práce se zabývá cestami řízenými gramatikami, gramatikami, které kladou omezení na cesty v derivačním stromě bezkontextové gramatiky. Cílem této diplomové práce je tvorba algoritmu pro převod mezi cestami řízenými gramatikami a stavovými gramatikami, což je jiný typ řízené gramatiky. Dalším cílem je na základě tohoto převodního algoritmu studovat vyjadřovací sílu cestami řízených gramatik. Převodní algoritmus je naimplementován v C++ a testován na sadě cestami řízených gramatik. Složitost algoritmu, jak časová, tak prostorová, je diskutována. Také nástroj pro syntaktickou analýzu cestami řízených gramatik je naimplementován. Složitost této analýzy je také diskutována.
|
|
|
Syntaktická analýza založená na regulovaných gramatikách
Vaníček, Luboš ; Kučera, Jiří (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce se zabývá regulovanými gramatikami. Popisuje vlastnosti různých druhů regulovaných gramatik a srovnává je. Ke srovnání využívá příklady postavené na kontextových jazycích. Práce se nejvíce zaměřuje na programované gramatiky. Modifikuje metody syntaktické analýzy a využívá je pro programované gramatiky. Práce aplikuje navrženou metodu syntaktické analýzy na kontextové jazyky a zkoumá jejich sílu.
|
|
|
One-Sided Random Context Grammars
Zemek, Petr ; Černá, Ivana (oponent) ; Doc. In.g Petr Sosík, Dr. (oponent) ; Meduna, Alexandr (vedoucí práce)
This thesis introduces the notion of a one-sided random context grammar as a context-free-based regulated grammar, in which a set of permitting symbols and a set of forbidding symbols are attached to every rule, and its set of rules is divided into the set of left random context rules and the set of right random context rules . A left random context rule can rewrite a nonterminal if each of its permitting symbols occurs to the left of the rewritten symbol in the current sentential form while each of its forbidding symbols does not occur there. A right random context rule is applied analogically except that the symbols are examined to the right of the rewritten symbol. The thesis is divided into three parts. The first part gives a motivation behind introducing one-sided random context grammars and places all the covered material into the scientific context. Then, it gives an overview of formal language theory and some of its lesser-known areas that are needed to fully grasp some of the upcoming topics. The second part forms the heart of the thesis. It formally defines one-sided random context grammars and studies them from many points of view. Generative power, relations to other types of grammars, reduction, normal forms, leftmost derivations, generalized and parsing-related versions all belong between the studied topics. The final part of this thesis closes its discussion by adding remarks regarding its coverage. More specifically, these remarks concern application perspectives, bibliography, and open problem areas.
|
|
|
Syntaktická analýza založená na stavových gramatikách
Novotný, Miroslav ; Kocman, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce se zabývá syntaktickou analýzou založenou na stavových gramatikách. Cílem je vytvořit program schopný načíst gramatiku ze vstupního souboru. Na základě této gramatiky vytvořit LL tabulku a následně i provést syntaktickou analýzu zadaného vstupu. Na těchto základech pak studovat vlastnosti metod syntaktické analýzy, založené na těchto gramatikách. Testování probíhá i na gramatických strukturách, které nejsou bezkontextové.
|
|
|
O vymazávacích pravidlech v řízených gramatikách
Zemek, Petr ; Koutný, Jiří (oponent) ; Meduna, Alexandr (vedoucí práce)
V této práci je diskutován vliv vymazávacích pravidel na generativní sílu řízených gramatik, což je velký otevřený problém teorie řízeného přepisování. Tato práce studuje možnost odstranění vymazávacích pravidel z těchto gramatik tak, že shromažďuje aktuální výsledky na toto téma a přináší novou podmínku, nazvanou k-limitované vymazávání, která zaručuje, že jsme bez vlivu na generovaný jazyk schopni odstranit všechna vymazávací pravidla z libovolné bezkontextové gramatiky řízené regulárním jazykem splňující tuto podmínku. Tento výsledek je částečným řešením výše zmíněného problému. Mimoto je prezentován nový algoritmus k odstranění vymazávacích pravidel z bezkontextových gramatik, který nepotřebuje předurčovat tzv. epsilon-neterminály (na rozdíl od standardního algoritmu používaného v učebnicích). V závěru je zhodnocen přínos těchto výsledků pro syntaktickou analýzu.
|
|
|
Regulated Grammar Systems
Tomko, Martin ; Kocman, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
This thesis recaps a basic theory of formal languages, regulated grammars, and the parsing of LL(1) languages. An algorithm for parsing programmed grammars inspired by LL(1) parsing is suggested and analyzed. The class of languages accepted by this algorithm is shown to be a strict superclass of LL(1) languages, containing some non-context-free languages. However, this class appears to be incomparable with the class of context-free languages.
|
|
|
Regulated Grammar Systems
Tomko, Martin ; Kocman, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
This thesis recaps a basic theory of formal languages, regulated grammars, and the parsing of LL(1) languages. An algorithm for parsing programmed grammars inspired by LL(1) parsing is suggested and analyzed. The class of languages accepted by this algorithm is shown to be a strict superclass of LL(1) languages, containing some non-context-free languages. However, this class appears to be incomparable with the class of context-free languages.
|
|
|
One-Sided Random Context Grammars
Zemek, Petr ; Černá, Ivana (oponent) ; Doc. In.g Petr Sosík, Dr. (oponent) ; Meduna, Alexandr (vedoucí práce)
This thesis introduces the notion of a one-sided random context grammar as a context-free-based regulated grammar, in which a set of permitting symbols and a set of forbidding symbols are attached to every rule, and its set of rules is divided into the set of left random context rules and the set of right random context rules . A left random context rule can rewrite a nonterminal if each of its permitting symbols occurs to the left of the rewritten symbol in the current sentential form while each of its forbidding symbols does not occur there. A right random context rule is applied analogically except that the symbols are examined to the right of the rewritten symbol. The thesis is divided into three parts. The first part gives a motivation behind introducing one-sided random context grammars and places all the covered material into the scientific context. Then, it gives an overview of formal language theory and some of its lesser-known areas that are needed to fully grasp some of the upcoming topics. The second part forms the heart of the thesis. It formally defines one-sided random context grammars and studies them from many points of view. Generative power, relations to other types of grammars, reduction, normal forms, leftmost derivations, generalized and parsing-related versions all belong between the studied topics. The final part of this thesis closes its discussion by adding remarks regarding its coverage. More specifically, these remarks concern application perspectives, bibliography, and open problem areas.
|
host ::
RSS.